#pragma once

#include "TypedList.h"

#define TREE_HANDLE_HEAD 0

template < class T > class SuperTree;
template < class T > class SuperNode;

//////// C L A S S   D E C L A R A T I O N S ////////////////////////

//-------------------------------------------------------------------
//                          SuperNode
//-------------------------------------------------------------------

template< class T > class SuperNode
{
	template <class U> friend class SuperTreeWalker;
	template <class U> friend class SuperTreeIter;
	template <class U> friend class SuperTree;

	public:

		SuperNode( T* pxData, SuperNode* pxParent, const bool bManagedMemory, const FHandle xHandle )
		{
			m_xHandle = xHandle;

			if( pxParent )
			{
				pxParent->AddChild( this );
			}

			m_pxParent = pxParent;
			m_pxChildren = new TypedList<SuperNode>( true );
			m_pxData = pxData;
		}

		~SuperNode()
		{
			if( m_bManagedMemory )
			{
				delete m_pxData;
				m_pxData = 0;
			}
			if( m_pxParent )
			{
				m_pxParent->RemoveChild( this );
			}
			delete m_pxChildren;
		}

		SuperNode* FindNode( const FHandle xHandle )
		{
			if( xHandle == m_xHandle )
			{
				return this;
			}

			for( u_int uChild = 0; uChild < m_pxChildren->Count(); ++uChild )
			{
				SuperNode* pxChild = m_pxChildren->Get( uChild );
				SuperNode<T>* pxFoundNode = pxChild->FindNode( xHandle );
				if( pxFoundNode )
				{
					return pxFoundNode;
				}
			}
			
			return 0;
		}

		SuperNode*					GetParent()			{ return m_pxParent; }
		const SuperNode*			GetParent() const	{ return m_pxParent; }
		void						SetParent( SuperNode* pxParent ) { m_pxParent = pxParent; }

		FHandle						GetHandle() const	{ return m_xHandle; }
		
		T*							GetData() 			{ return m_pxData; }

	private:

		void AddChild( SuperNode* pxChild )
		{
			m_pxChildren->Add( pxChild );
			pxChild->SetParent( this );
		}

		void InsertChildBefore( SuperNode* pxChild, SuperNode* pxBefore )
		{
			int iIndex = m_pxChildren->IndexOf( pxBefore );
			if( iIndex == -1 )
			{
				return;
			}

			m_pxChildren->InsertBefore( iIndex, pxChild );
			pxChild->SetParent( this );
		}

		void InsertChildAfter( SuperNode* pxChild, SuperNode* pxAfter )
		{
			int iIndex = m_pxChildren->IndexOf( pxAfter );
			if( iIndex == -1 )
			{
				return;
			}

			m_pxChildren->InsertAfter( iIndex, pxChild );
			pxChild->SetParent( this );
		}

		void RemoveChild( SuperNode* pxChild )
		{
			m_pxChildren->Remove( pxChild );
			if( pxChild->GetParent() == this )
			{
				pxChild->SetParent( 0 );
			}
		}

		TypedList<SuperNode>*		GetChildren()		{ return m_pxChildren; }
		const TypedList<SuperNode>* GetChildren() const { return m_pxChildren; }

		TypedList<SuperNode>* m_pxChildren;
		SuperNode* m_pxParent;
		T* m_pxData;
		FHandle m_xHandle;
		bool m_bManagedMemory;
};

//-------------------------------------------------------------------
//                          SuperTree
//-------------------------------------------------------------------

template <class T> class SuperTree
{
	template <class U> friend class SuperTreeIter;
	template <class U> friend class SuperTreeWalker;

	public:

		SuperTree( const bool bManageMemory = false )
		{
			m_bManageMemory = bManageMemory;
			m_pxHead = new SuperNode<T>( 0, 0, bManageMemory, TREE_HANDLE_HEAD );
		}

		~SuperTree()
		{
			delete m_pxHead;
		}

		FHandle Add( T* pxItem, const FHandle xParent = TREE_HANDLE_HEAD, const FHandle xSpecifyHandle = INVALID_HANDLE )
		{
			// Find the parent node
			SuperNode<T>* pxParent = m_pxHead->FindNode( xParent );

			FHandle xNewHandle = xSpecifyHandle;
			if( xNewHandle == INVALID_HANDLE )
			{
				xNewHandle = ++s_xLastHandle;
			}
			else
			{
				// Max sure the FHandle counter is bigger than any existing handles to avoid conflicts
				s_xLastHandle = MACRO_MAX( xSpecifyHandle + 1, s_xLastHandle );
			}

			SuperNode<T>* pxNode = new SuperNode<T>( pxItem, pxParent, m_bManageMemory, xNewHandle );

			return pxNode->GetHandle();
		}

		T* Get( const FHandle xHandle )
		{
			SuperNode<T>* pxNode = m_pxHead->FindNode( xHandle );
			if( pxNode )
			{
				return pxNode->GetData();
			}
			return 0;
		}

		void Delete ( const FHandle xHandle )
		{
			SuperNode<T>* pxNode = m_pxHead->FindNode( xHandle );

			delete pxNode;
		}

		FHandle FindParent( const FHandle xHandle )
		{
			SuperNode<T>* pxNode = m_pxHead->FindNode( xHandle );

			if( !pxNode )
			{
				return INVALID_HANDLE;
			}

			SuperNode<T>* pxParent = pxNode->GetParent();
			if( !pxParent )
			{
				return TREE_HANDLE_HEAD;
			}

			return pxParent->GetHandle();
		}

		void Move( const FHandle xHandle, const FHandle xNewParent = TREE_HANDLE_HEAD, const FHandle xMoveAfter = INVALID_HANDLE )
		{
			// Do some parameter validation

			SuperNode<T>* pxNode = m_pxHead->FindNode( xHandle );
			SuperNode<T>* pxNewParentNode = m_pxHead->FindNode( xNewParent );
			SuperNode<T>* pxMoveAfterNode = m_pxHead->FindNode( xMoveAfter );

			if( !pxNode )
			{
				return;
			}

			if( xNewParent != INVALID_HANDLE && !pxNewParentNode )
			{
				return;
			}

			if( xMoveAfter != INVALID_HANDLE && !pxMoveAfterNode )
			{
				return;
			}
			
			if( !pxNewParentNode )
			{
				// If there is no new parent run the same logic with the existing parent
				pxNewParentNode = pxNode->GetParent();
			}

			// Remove the node from its existing parent

			SuperNode<T>* pxParent = pxNode->GetParent();
			if( pxParent )
			{
				pxParent->RemoveChild( pxNode );
			}

			// Insert the node under its new parent
			
			if( pxMoveAfterNode )
			{
				// If the node to move after exists, insert after it...
				pxNewParentNode->InsertChildAfter( pxNode, pxMoveAfterNode );
			}
			else
			{
				pxNewParentNode->AddChild( pxNode );
			}
		}


		FHandle InsertAfter( T* pxItem, const FHandle xParent = TREE_HANDLE_HEAD, const FHandle xInsertAfter = INVALID_HANDLE )
		{
			FHandle xNewNode = Add( pxItem, xParent );

			if( xNewNode == INVALID_HANDLE )
			{
				return INVALID_HANDLE;
			}

			Move( xNewNode, xParent, xInsertAfter );

			return xNewNode;
		}

		void Clear ()
		{
			delete m_pxHead;
			m_pxHead = new SuperNode<T>( 0, 0, m_bManageMemory, TREE_HANDLE_HEAD );
		}

		u_int GetNodeDepth( FHandle xHandle ) const
		{
			u_int uDepth = 0;
			SuperNode<T>* pxNode = m_pxHead->FindNode( xHandle );
			while( pxNode )
			{
				pxNode = pxNode->GetParent();
				++uDepth;
			}
			if( uDepth != 0 )
			{
				uDepth -= 2;
			}
			return uDepth;
		}

	private:

		SuperNode<T>*	m_pxHead;
		bool			m_bManageMemory;
		static FHandle	s_xLastHandle;
};

//-------------------------------------------------------------------
//                          SuperTreeWalker
//-------------------------------------------------------------------

template <class T> class SuperTreeWalker
{
	// Note: This is a pretty expensive tree walker, so dont use it for enormous trees

	// Tree is walked in this order:
	//
	//             1
	//            / \
	//           2   5
	//          / \
	//         3   4
	//
	// You can also provide a callback to decide if the walker should
	// recurse into each node's children

	typedef bool (*SuperTreeWalker_RecurseCallback)( const T* pxItem );

	public:

		SuperTreeWalker( SuperTree<T>* pxTree, const FHandle xTop = TREE_HANDLE_HEAD )
		{
			m_pxTree = pxTree;
			m_xTop = xTop;
			m_xCurrent = xTop;
			m_bDone = false;
			m_pfnRecurseCallback = 0;

			Next();
		}

		void SetShouldRecurseCallback( SuperTreeWalker_RecurseCallback pfnCallback )
		{
			m_pfnRecurseCallback = pfnCallback;
		}

		static SuperTreeWalker_RecurseCallback GetNoRecursionCallback()
		{
			return SuperTreeWalker_DoNotRecurse;
		}

		T* Get ( const bool bProgress = false )
		{
			if( Done() )
			{
				return 0;
			}

			T* pxRet = 0;
			if( m_pxTree )
			{
				pxRet = m_pxTree->Get( m_xCurrent );
			}

			if( bProgress )
			{
				Next();
			}

			return pxRet;
		}

		FHandle GetHandle ( const bool bProgress = false )
		{
			if( Done() )
			{
				return INVALID_HANDLE;
			}

			FHandle xRet = m_xCurrent;

			if( bProgress )
			{
				Next();
			}

			return xRet;
		}

		bool Next()
		{
			if( Done() || !m_pxTree )
			{
				return false;
			}

			// Step 1: Do I have children?
			// ---------------------------
			
			SuperNode<T>* pxNode = m_pxTree->m_pxHead->FindNode( m_xCurrent );

			if( !pxNode )
			{
				return false;
			}

			TypedList<SuperNode<T> > * pxChildren;

			if( !m_pfnRecurseCallback || m_pfnRecurseCallback( pxNode->GetData() ) )
			{
				pxChildren = pxNode->GetChildren();

				if( pxChildren )
				{
					// I do have children, next is the first child
					SuperNode<T>* pxChild = pxChildren->Get( 0 );

					if( pxChild )
					{
						// Set the current FHandle and return;
						m_xCurrent = pxChild->GetHandle();
						return true;
					}
				}
			}

			// Step 2: Do I have siblings?
			// ---------------------------
			
			// Get the parent of the current node
			FHandle xParent = m_pxTree->FindParent( m_xCurrent );

			if( xParent == INVALID_HANDLE )
			{
				m_bDone = true;
				return false;
			}

			// Get the children for the parent so I can find my siblings
			SuperNode<T>* pxParentNode = m_pxTree->m_pxHead->FindNode( xParent );

			if( !pxParentNode )
			{
				m_bDone = true;
				return false;
			}

			pxChildren = pxParentNode->GetChildren();

			if( !pxChildren )
			{
				m_bDone = true;
				return false;
			}

			// loop over and find myself
			bool bFoundMyself = false;
			for( u_int uNode = 0; uNode < pxChildren->Count(); ++uNode )
			{
				SuperNode<T>* pxSibling = pxChildren->Get( uNode );
				
				if( bFoundMyself )
				{
					// This is the first sibling after the current, set it to the current
					m_xCurrent = pxSibling->GetHandle();
					return true;
				}

				if( pxSibling->GetHandle() == m_xCurrent )
				{
					// This is me, I should set the next sibling to the current
					bFoundMyself = true;
				}
			}

			// Step 3: Does my parent have siblings?
			// -------------------------------------

			for(;;)	// while(1) gives warning C4127
			{
				if( xParent == m_xTop )
				{
					m_bDone = true;
					return false;
				}

				SuperNode<T>* pxGrandParent = 0;

				// Grab my parent
				pxParentNode = m_pxTree->m_pxHead->FindNode( xParent );
				// Grab my grandparent
				pxGrandParent = pxParentNode->GetParent();

				if( !pxGrandParent )
				{
					m_bDone = true;
					return false;
				}

				pxChildren = pxGrandParent->GetChildren();

				if( !pxChildren )
				{
					// Parent has no siblings, go up
					xParent = pxGrandParent->GetHandle();
					continue;
				}

				// Find the parent in the grandparent children
				bool bFoundParent = false;
				for( u_int uNode = 0; uNode < pxChildren->Count(); ++uNode )
				{
					SuperNode<T>* pxParentSibling = pxChildren->Get( uNode );
					
					if( bFoundParent )
					{
						// This is the next sibling of the parent, use it
						m_xCurrent = pxParentSibling->GetHandle();
						return true;
					}

					if( pxParentSibling->GetHandle() == xParent )
					{
						// This is my parent, pick its next sibling
						bFoundParent = true;
					}
				}

				// If we got here the parent has no siblings, so go up another level
				xParent = pxGrandParent->GetHandle();
			}
		}

		bool Done() const
		{
			return m_bDone;
		}

	private:

		static bool SuperTreeWalker_DoNotRecurse( const T* pxItem )
		{
			return false;
		}

		SuperTree<T>* m_pxTree;
		FHandle m_xTop;
		FHandle m_xCurrent;
		bool m_bDone;
		SuperTreeWalker_RecurseCallback m_pfnRecurseCallback;
};

//-------------------------------------------------------------------
//                          SuperTreeIter
//-------------------------------------------------------------------

template <class T> class SuperTreeIter
{
	public:

		SuperTreeIter( SuperTree<T>* pxTree, const FHandle xParent = TREE_HANDLE_HEAD )
		{
			m_uCurrentItem = 0;
			m_pxChildren = 0;

			if( pxTree )
			{
				if( xParent == TREE_HANDLE_HEAD )
				{
					m_pxChildren = pxTree->m_pxHead->GetChildren();
				}
				else
				{
					SuperNode<T>* pxNode = pxTree->m_pxHead->FindNode( xParent );
					if( pxNode )
					{
						m_pxChildren = pxNode->GetChildren();
					}
				}
			}
		}

		T* Get ( const bool bProgess = false )
		{
			if( Done() )
			{
				return 0;
			}

			SuperNode<T>* pxNode = m_pxChildren->Get( m_uCurrentItem );
			if( bProgess )
			{
				++m_uCurrentItem;
			}

			return pxNode->GetData();
		}

		FHandle GetHandle ( const bool bProgress = false )
		{
			if( Done() )
			{
				return INVALID_HANDLE;
			}

			SuperNode<T>* pxNode = m_pxChildren->Get( m_uCurrentItem );
			if( bProgress )
			{
				++m_uCurrentItem;
			}

			return pxNode->GetHandle();
		}

		bool Next()
		{
			if( !Done() )
			{
				++m_uCurrentItem;
				return true;
			}
			return false;
		}

		bool Done() const
		{
			if( !m_pxChildren )
			{
				return true;
			}

			if( m_pxChildren->Count() == 0 )
			{
				return true;
			}

			return m_pxChildren->Count() == m_uCurrentItem;
		}

	private:

		TypedList<SuperNode<T> >* m_pxChildren;
		u_int m_uCurrentItem;
};

//////// S T A T I C   M E M B E R   V A R I A B L E S //////////////

template<class T> FHandle SuperTree<T>::s_xLastHandle = 1;

//eof
